/**
 * 
 */
package string.passed;

/**
 * @author xyyi
 *
 */
public class RegularExpression {

	/**
	 Implement regular expression matching with support for '.' and '*'.

	'.' Matches any single character.
	'*' Matches zero or more of the preceding element.
	
	The matching should cover the entire input string (not partial).
	
	The function prototype should be:
	bool isMatch(const char *s, const char *p)
	
	Some examples:
	isMatch("aa","a") ? false
	isMatch("aa","aa") ? true
	isMatch("aaa","aa") ? false
	isMatch("aa", "a*") ? true
	isMatch("aa", ".*") ? true
	isMatch("ab", ".*") ? true
	isMatch("aab", "c*a*b") ? true
	
	isMatch("a", "b*a") ? true
	 */
	public boolean isMatch(String s, String p) {
		// Start typing your Java solution below
		// DO NOT write main() function
		return isMatch(s, p, 0, 0);
	}

	private boolean isMatch(String s, String p, int si, int pi) {

		if (p.length() == pi)
			return s.length() == si;

		if (s.length() == si) {
			if (pi < p.length() - 1 && p.charAt(pi + 1) == '*') {
				while (++pi < p.length() && p.charAt(pi) == '*')
					;
				return isMatch(s, p, si, pi);
			}
			return false;
		}

		if (pi < p.length() - 1 && p.charAt(pi + 1) == '*') {
			if ((s.charAt(si) == p.charAt(pi) || p.charAt(pi) == '.')
					&& isMatch(s, p, si + 1, pi))
				return true;
			while (++pi < p.length() && p.charAt(pi) == '*')
				;
			return isMatch(s, p, si, pi);
		} else if (s.charAt(si) == p.charAt(pi) || p.charAt(pi) == '.')
			return isMatch(s, p, si + 1, pi + 1);

		return false;
	}

	// good for interview
	public boolean isMatch1(String s, String p, int si, int pi) {

		// if pattern is empty, match is decided by string (empty string return true otherwise false)
		if (p.length() == pi)
			return s.length() == si;

		if (s.length() == si) {
			if (pi < p.length() - 1 && p.charAt(pi + 1) == '*') {
				pi++;
				while (pi < p.length() && p.charAt(pi) == '*')
					pi++;
				return isMatch(s, p, si, pi);
			}
			return false;
		}

		if (pi < p.length() - 1 && p.charAt(pi + 1) == '*') {
			if ((s.charAt(si) == p.charAt(pi) || p.charAt(pi) == '.')
					&& isMatch(s, p, si + 1, pi)) // it can match more s[si]
				return true;
			pi++;
			while (pi < p.length() && p.charAt(pi) == '*')
				// skip s[si]
				pi++;
			return isMatch(s, p, si, pi);
		} else {
			if (p.charAt(pi) == '.' || p.charAt(pi) == s.charAt(si))
				return isMatch(s, p, si + 1, pi + 1);
			else
				return false;
		}

		//return false;
	}

	/**
	 * Another 
	 * http://codereview.stackexchange.com/questions/10776/better-implementation-of-a-simplified-regular-expression-engine
	 */

	/**
	 * 
	 */
	public RegularExpression() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		RegularExpression re = new RegularExpression();
		String[] s = { "ab" };
		String[] p = { ".*c" };
		for (int i = 0; i < s.length; i++) {
			System.out.printf("'%s' '%s' is match: %b", s[i], p[i],
					re.isMatch(s[i], p[i]));
		}

	}

}
